package indi.gao.leetcode.tree;

import lombok.Data;
import lombok.Getter;

/**
 * @Description:二叉树的最长路径
 * @create: 2020/4/19 23:19
 * @update logs
 * @throws Exception
 */
public class LongestPath {

    public static void main(String[] args) {
        Node node = null;
        node = initBinary(node);

        frontOrder(node);
        System.out.println();
        midOrder(node);
        System.out.println();
        tailOrder(node);
    }


    /**
     * 非递归深度遍历
     */


    /**
     * 前序遍历二叉树(根节点->左节点->右节点)
     */
    public static void frontOrder(Node node) {
        if (node == null) {
            return;
        } else {
            System.out.print(node.getData() + ">");
            // 遍历左子树
            frontOrder(node.getLeft());
            frontOrder(node.getRight());
        }
    }

    /**
     * 中序遍历二叉树（左节点->根节点->右节点）
     */
    public static void midOrder(Node node) {
        if (node == null) {
            return;
        } else {
            midOrder(node.getLeft());
            System.out.print(node.getData() + ">");
            midOrder(node.getRight());
        }
    }

    /**
     * 后序遍历二叉树(左->右->跟)
     */
    public static void tailOrder(Node node) {
        if (node == null) {
            return;
        } else {
            tailOrder(node.getLeft());
            tailOrder(node.getRight());
            System.out.print(node.getData() + ">");
        }
    }

    /**
     * 初始化二叉树
     * <p>
     * 0
     * 3      6
     * 1   2  4   5
     */
    public static Node initBinary(Node node) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node3.setLeft(node1);
        node3.setRight(node2);

        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node6.setLeft(node4);
        node6.setRight(node5);

        node = new Node(0);
        node.setRight(node6);
        node.setLeft(node3);

        return node;
    }

}

/**
 * 节点定义
 */
@Data
class Node {
    private Node left;
    private Node right;
    @Getter
    private int data;

    Node(int data) {
        this.data = data;
    }
}
